#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;

const int MAXM = 105;
const int INF = INT_MAX;


const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

struct Node {
    int x, y;        
    int cost;        
    int lastColor;   
    bool used;  
    
    
    bool operator>(const Node& other) const {
        return cost > other.cost;
    }
};

int m, n;
int grid[MAXM][MAXM];      
int dist[MAXM][MAXM][2][3]; 

void init() {
    
    memset(grid, -1, sizeof(grid));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k < 2; k++) {
                for (int l = 0; l < 3; l++) {
                    dist[i][j][k][l] = INF;
                }
            }
        }
    }
}

int bfs() {
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    
    
    Node start;
    start.x = 1;
    start.y = 1;
    start.cost = 0;
    start.lastColor = grid[1][1];  
    start.used = false;
    
    dist[1][1][0][grid[1][1]] = 0;
    pq.push(start);
    
    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        
        int x = current.x;
        int y = current.y;
        int cost = current.cost;
        int lastColor = current.lastColor;
        bool used = current.used;
        
        
        if (cost > dist[x][y][used][lastColor]) {
            continue;
        }
        
        
        if (x == m && y == m) {
            return cost;
        }
        
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            
            if (nx < 1 || nx > m || ny < 1 || ny > m) {
                continue;
            }
            
            int nxtColor = grid[nx][ny];
            if (nxtColor != -1) {
                int addCost = 0; 
                if (lastColor != nxtColor) {
                    addCost = 1;
                }
                int newCost = cost + addCost;
                int newLastColor = nxtColor;
                bool newused = false;  
                if (newCost < dist[nx][ny][newused][newLastColor]) {
                    dist[nx][ny][newused][newLastColor] = newCost;
                    Node nxt;
                    nxt.x = nx;
                    nxt.y = ny;
                    nxt.cost = newCost;
                    nxt.lastColor = newLastColor;
                    nxt.used = newused;
                    pq.push(nxt);
                }
            }
            
            else if (nxtColor == -1 && !used) {
                int magicCost = 2;
                for (int magicColor = 0; magicColor <= 1; magicColor++) {
                    
                }
            }
        }
    }
    return -1;  
}

int main() {
    cin >> m >> n;
    init();
    for (int i = 0; i < n; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        grid[x][y] = c;
    }
    int result = bfs();
    cout << result << endl;
}
